package com.datastructures2.graph.无向图;

import com.datastructures.graph.Bag;
import edu.princeton.cs.algs4.In;

/**
 * @author MaoLin Wang
 * @date 2020/2/2113:05
 */
public class Graph {
    /**
     * 顶点数目
     */
    private final int V;
    /**
     * 边的数目
     */
    private int E;
    /**
     * 邻接表
     */
    private Bag<Integer>[] adj;

    public Graph(int v) {
        V = v;
        this.E=0;
        adj=new Bag[V];
        for (int i = 0; i < V; i++) {
            adj[i]=new Bag<>();
        }
    }
    public boolean hasEdge(int v,int w){
        for(int x:adj(v)){
            if (x==w){
                return true;
            }
        }
        return false;
    }

    public Graph(In in) {
        this(in.readInt());
        int E=in.readInt();
        for (int i = 0; i < E; i++) {
            int v=in.readInt();
            int w=in.readInt();
        }
    }
    public int V(){
        return V;
    }
    public int E(){
        return E;
    }
    public void addEdge(int v,int w){
        //不允许有自环
        if (v==w){
            return;
        }else if (hasEdge(v,w)){//不允许有平行边
            return;
        }else {
            adj[v].add(w);
            adj[w].add(v);
            E++;
        }

    }
    public  int degree(int v){
        int degree=0;
        for (int w:adj(v)){
            degree++;
        }
        return degree;
    }
    public  int maxDegree(){
        int max=0;
        for (int v = 0; v < V; v++) {
            int degree = degree(v);
            if (degree>max){
                max=degree;
            }
        }
        return max;
    }
    public int numOfSelfLoops(Graph graph){
        int loops=0;
        for (int i = 0; i < graph.V(); i++) {
            for(int w:graph.adj(i)){
                if (w==i){
                    loops++;
                }
            }
        }
        return loops/2;
    }

    public Iterable<Integer> adj(int v){
        return adj[v];
    }

    @Override
    public String toString() {
       StringBuilder sb=new StringBuilder(V+"个顶点,"+E+"条边\n");
        for (int i = 0; i < V; i++) {
             sb.append(i+" : ");
             for(int w: this.adj(i)){
                 sb.append(w+" ") ;
             }
             sb.append("\n");
        }
        return sb.toString();
    }
}
